package exercises.newcoder.solution;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=188&&tqId=38635&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC126 换钱的最少货币数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
 * 如果无解，请返回-1.
 * <p>
 * 数据范围：数组大小满足  ， 数组中每个数字都满足 ，
 * <p>
 * 要求：时间复杂度  ，空间复杂度 。
 * <p>
 * 示例1
 * 输入：
 * [5,2,3],20
 * <p>
 * 返回值：
 * 4
 * <p>
 * 示例2
 * 输入：
 * [5,2,3],0
 * <p>
 * 返回值：
 * 0
 * <p>
 * 示例3
 * 输入：
 * [3,5],2
 * <p>
 * 返回值：
 * -1
 * <p>
 * 备注：
 * <li>0 \leq n \leq 1\,0000≤n≤1000</li>
 * <li>0 \leq aim \leq 5\,0000≤aim≤5000</li>
 *
 * @author or2
 * @date 2021年10月03日 时间: 8:49
 */
public class MinMoney {
    private Map<Integer, Integer> memory = new HashMap<>();

    /**
     * 最少货币数
     *
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney(int[] arr, int aim) {
        if (arr.length == 0)
            return -1;

        if (aim < 0)
            return -1;
        if (aim == 0)
            return 0;

        int res = Integer.MAX_VALUE;
        for (int money : arr) {
            int coins;
            if (memory.containsKey(aim - money))
                coins = memory.get(aim - money);
            else
                coins = minMoney(arr, aim - money);
            if (coins >= 0 && coins < res)
                res = coins;
        }

        if (res == Integer.MAX_VALUE)
            res = -2;
        memory.put(aim, res + 1);
        return res + 1;
    }

    public int dp(int[] arr, int aim) {
        if (arr.length == 0)
            return -1;
        if (aim == 0)
            return 0;

        int[] dp = new int[aim];
        Arrays.sort(arr);
        for (int coin : arr)
            if (coin > dp.length)
                break;
            else
                dp[coin - 1] = 1;

        for (int money = 0, length = dp.length; money < length; money++) {
            if (dp[money] == 0)
                continue;
            for (int coin : arr) {
                int nextAim = coin + money;
                if (nextAim >= length) {
                    break;
                } else if (dp[nextAim] == 0 || dp[nextAim] > dp[money] + 1)
                    dp[nextAim] = dp[money] + 1;
            }
        }

        return dp[aim - 1] == 0 ? -1 : dp[aim - 1];
    }

    public int quick(int[] arr, int aim) {
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, 1, dp.length, aim + 1);

        for (int i = 0, arrLength = arr.length; i < arrLength; i++) {
            int coin = arr[i];
            for (int j = coin; j <= aim; j++) {
                if (dp[j] > dp[j - coin] + 1)
                    dp[j] = dp[j - coin] + 1;
            }
        }

        return dp[aim] == aim + 1? -1: dp[aim];
    }

}
